package airthmetic.exercise.bit;

public class _52_N皇后II {
    public int total = 0;
    public int totalNQueens(int n) {
        dfs(n,0,0,0,0);
        return total;
    }

    public void dfs(int n, int dept, int col, int pie, int na){
        // terminal
        if(dept == n){
            total++;
            return;
        }
        // 求出都哪里可以放置皇后 0表示不能放置 1表示能放置
        int bits = ~(col|pie|na) & ((1<<n) -1);

        // 不为0之前都可以继续放置皇后
        while(bits > 0){
            // 求出这一次放置皇后的位置
            int mask = bits & (-bits);
            // 将这次放皇后的位置置为不能放置皇后
            bits = bits &(bits - 1);
            // drill donw
            dfs(n,dept+1,col | mask, (pie | mask) >> 1, (na | mask) << 1);
        }



    }

}
